<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<!-- DW6 -->
<head>
<!-- Copyright 2005 Macromedia, Inc. All rights reserved. -->
<title>Text</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link rel="stylesheet" href="../mm_health_nutr.css" type="text/css">
<script language="javascript">
//--------------- LOCALIZEABLE GLOBALS ---------------
var d=new Date();
var monthname=new Array("January","February","March","April","May","June","July","August","September","October","November","December");
//Ensure correct for language. English is "January 1, 2004"
var TODAY = monthname[d.getMonth()] + " " + d.getDate() + ", " + d.getFullYear();
//---------------   END LOCALIZEABLE   ---------------
</script>
</head>
<body bgcolor="#F4FFE4">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
  <tr bgcolor="#D5EDB3">
    <td colspan="2" rowspan="2">&nbsp;</td>
    <td width="494" height="50" id="logo" valign="bottom" align="center" nowrap>Misioneros y caníbales</td>
    <td width="103">&nbsp;</td>
  </tr>

  <tr bgcolor="#D5EDB3">
    <td height="19" id="tagline" valign="top" align="center">Grupo 15</td>
	<td width="103">&nbsp;</td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#5C743D"><img src="mm_spacer.gif" alt="" width="1" height="2" border="0"></td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#99CC66" background="mm_dashed_line.gif"><img src="mm_dashed_line.gif" alt="line decor" width="4" height="3" border="0"></td>
  </tr>

  <tr bgcolor="#99CC66">
  <td>&nbsp;</td>
  	<td colspan="3" id="dateformat" height="20"><a href="../index.html">INDICE</a>&nbsp;&nbsp;::&nbsp;&nbsp;<a href="../arquitectura.html#juegos">JUEGOS&nbsp; </a>::&nbsp;&nbsp;<script language="javascript">
      document.write(TODAY);	</script>	</td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#99CC66" background="mm_dashed_line.gif"><img src="mm_dashed_line.gif" alt="line decor" width="4" height="3" border="0"></td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#5C743D"><img src="mm_spacer.gif" alt="" width="1" height="2" border="0"></td>
  </tr>
 <tr>
    <td width="40">&nbsp;</td>
    <td colspan="2" valign="top">&nbsp;<br>
    &nbsp;<br>
    <table border="0" cellspacing="0" cellpadding="2" width="791">
        <tr>
          <td width="787" class="pageName">Misioneros vs. Caníbales</td>
        </tr>
        <tr>
          <td class="bodyText">
			<ul>
				<li><font size="3">Descripción del juego:</font></li>
			</ul>
			<p align="justify">Debemos pasar 3 caníbales y 3 misioneros de una 
			orilla del río a la otra, mediante una barca que sólo tiene 2 plazas 
			para ser ocupadas, teniendo en cuenta que hay que evitar que el/los 
			caníbal/es devore a un/los misionero/s. En cada estado se debe 
			conocer la posición de cada uno de los 7 elementos, siendo el 7º 
			elemento la barca, la cual no puede moverse vacía, por lo que cada 
			estado estará representado como una tupla de 3 elementos que indican 
			la cantidad de misioneros existentes en la orilla inicial, la 
			cantidad de caníbales en dicha orilla y la posición de la barca, 
			pudiendo ser el lado izquierdo o derecho del río.</p>
			<p align="center"><img border="0" src="images/mision5.jpg"></p>
		  <ul>
				<li>
				<p align="justify"><font size="3">Operadores</font></p></li>
			</ul>
			<p align="justify">Todos los operadores suponen como requisito que 
			la barca este ocupada para poder moverse de una orilla a la otra.</p>
			<ol>
				<li>
				<p align="justify">Cruza un caníbal desde la orilla izquierda.</li>
				<li>
				<p align="justify">Cruza un caníbal desde la orilla derecha.</li>
				<li>
				<p align="justify">Cruzan dos caníbales desde la orilla 
				izquierda.</li>
				<li>
				<p align="justify">Cruzan dos caníbales desde la orilla derecha.</li>
				<li>
				<p align="justify">Cruza un misionero desde la orilla izquierda.</li>
				<li>
				<p align="justify">Cruza un misionero desde la orilla derecha.</li>
				<li>
				<p align="justify">Cruzan dos misioneros desde la orilla 
				izquierda</li>
				<li>
				<p align="justify">Cruzan dos misioneros desde la orilla 
				derecha.</li>
			</ol>
			<ul>
				<li>
				<p align="justify"><font size="3">Algoritmo</font></p></li>
			</ul>
			<p align="justify">Algoritmo DepthLimitedSearch o Profundidad 
			limitada: Basada en la búsqueda primero en profundidad, pero fijando 
			un límite l de profundidad, para evitar descender infinitamente. 
			Éste límite permite desechar caminos en los que el estado objetivo 
			es muy lejano del nodo inicial. En este caso, el límite de 
			profundidad es 11. </p>
			<p align="justify">Se utiliza un algoritmo de búsqueda desinformada, 
			evitando así la necesidad de implementar una función heurística y 
			ampliando la variedad de los algoritmos que se usen. Profundidad 
			limitada permite obtener una solución siempre que se establezca un 
			límite de profundidad suficiente para realizar el mínimo número de 
			transportes necesarios para conseguir el objetivo del juego, en este 
			caso, el límite de profundidad es 11, esto implica que la solución 
			encontrada tendrá 11 movimientos aunque no se asegura, mediante el 
			algoritmo, que hayan caminos más cortos, pero habiendo probado 
			diferentes límites, incluso limites inferiores se demuestra que el 
			camino más corto y por tanto se genera, aunque no a través de la 
			propia búsqueda, la optimización de la solución</p>
			<p align="center"><img border="0" src="images/mision6.jpg"></p>
		  <ul>
				<li>
				<p align="justify"><font size="3">Espacio de estados</font></p>
				</li>
			</ul>
			<p align="justify">Estado( Número de misioneros en la orilla 
			izquierda, Número de caníbales en la orilla izquierda, Posición de 
			la barca )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Número de misioneros en la orilla izquierda: {0, 1, 2, 3}<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Número de caníbales en la orilla izquierda: {0, 1, 2, 3}<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Posición de la barca: True (Orilla izquierda) <sup>v</sup> False 
			(Orilla derecha)<br>						
			
			<p align="justify">Basta con conocer el número de misioneros y el 
			número de caníbales en una de las orillas, ya sea la orilla final o 
			final, ya que se puede obtener tanto el número de misioneros como de 
			caníbales en la otra orilla, mediante operaciones aritméticas e 
			incluyendo como datos el operador que se ejecute en cada paso, ya 
			que éste aporta información debido a que en ningún caso puede 
			existir un movimiento de la barca, entre orilla y orilla, vacía. Por 
			tanto, al tratarse de un espacio de estados bastante extenso debido 
			al gran numero de variedades que se pueden generar mediante el uso 
			de los distintos operadores ( 8 ), se crea una representación con la 
			información mínima y ampliable a través de operaciones aritméticas.<p align="justify">
			Estados inalcanzables:<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 0, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 2, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 3, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 0, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 1, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 3, Izquierda )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 0, Derecha )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 2, Derecha )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 1, 3, Derecha )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 0, Derecha )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 1, Derecha )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 2, 3, Derecha )<br>
			
			
			<p align="justify">Estado inicial:<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 3, 3, Izquierda)<p align="justify">Estado final:<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( 0, 0, Derecha)</td>
		</tr>
        <tr>
          <td class="bodyText"><span class="pageName">Diagrama UML</span></td>
        </tr>
        <tr>
          <td class="bodyText"><p>A continuacion se expone el diagrama uml de este juego para aportar informacion adicional sobre su implementacion.</p>
          <p align="center"><img src="images/Canibal.jpg" alt="UML Misioneros y canibales" width="698" height="1377"></p></td>
        </tr>
      </table>
  </tr>

 <tr>
    <td width="40">&nbsp;</td>
    <td width="110">&nbsp;</td>
    <td width="494">&nbsp;</td>
	<td width="103">&nbsp;</td>
  </tr>
</table>
</body>
</html>
